This application relates to computer communication networks for interconnecting computers and, specifically, to routing in bridged networks.
Computer interconnection and communication systems are typically referred to as networks. Networks are generally classified according to their geographical extent as local area networks (LANs), metropolitan area networks (MANs) and wide area networks (WANs).
LANs are commonly used to transmit messages between relatively closely located computers. LANs are characterized by several basic types of organizational architectures including linear, ring and mesh. For example, Ethernet is a widely used linear LAN and FDDI (fiber distributed data interface) is a widely used ring LAN. Unlike linear and ring LANs, mesh LANs have an arbitrary topology. One mesh LAN architecture is described in U.S. Pat. No. 5,088,091, entitled xe2x80x9cHIGH-SPEED MESH CONNECTED LOCAL AREA NETWORK,xe2x80x9d issued on Feb. 11, 1992 to Michael D. Schroeder et al., and U.S. Pat. No. 5,138,615, entitled xe2x80x9cRECONFIGURATION SYSTEM AND METHOD FOR HIGH-SPEED MESH CONNECTED LOCAL AREA NETWORK,xe2x80x9d issued on Apr. 11, 1992, to Leslie B. Lamport et al., both of which are hereby incorporated by reference.
A LAN is a shared transmission medium, such as a continuous conductor, that connects some number of addressable devices, such as printers, servers, and workstations. The addressable devices are called stations. Special attention is paid to LANs, such as Ethernet, in which each station has a globally unique and unchanging address, called its unique identifier (UID).
Stations on a LAN communicate by sending and receiving data packets or groups of data packets. In general, a packet contains the station address, UID, of the packet source, the station address UID of the packet destination and a payload. Packets can be distinguished by their destination address type. For example, a unicast packet is a packet with a station address as its destination. Stations on a LAN can also communicate by sending a packet to a group of destinations. In this case the packet has a group address UID as its destination and is called a multicast packet. Typically one bit in the UID is dedicated to distinguish station addresses from group addresses. Typically also one particular group address is dedicated to signify the group of all stations. A multicast packet with a group address of all the stations as its destination is called a broadcast packet.
LANs have basic limitations such as the number of stations, bandwidth and physical extent. A LAN offers, however, a useful high-speed communication service that facilitates data sharing and client-server interactions among its stations. In order to extend the benefits of a LAN beyond the basic limitations of a single LAN, forwarding devices, known as bridges, are used to interconnect LANs to form extended LANs.
An extended LAN is a collection of LANs interconnected by bridges. Bridges are addressable devices that forward packets back and forth between the bridged LANs. An extended LAN architecture with bridged LANs is referred to as a bridged network architecture. Each of the individual component LANs is known as a network segment. The network segment is also simply referred to as the segment.
Since bridges are addressable devices, they are stations on each of their connected LANs. Stations that are not bridges are known as end stations. For simplicity, end stations are also called hosts.
A bridge includes a plurality of bridge ports, each one corresponding to a connection between the bridge and a segment. Bridge functions that pertain to a specific connection between the bridge and a segment are typically described as being performed by the corresponding port.
In general, a single bridge may connect to any number of LANs, although typically a bridge connects to a small number of LANs, say between two and eight. Notwithstanding hosts, an extended LAN consists of segments, bridges and the connections between segments and bridges.
Structurally, an extended LAN can be represented as a graph. A graph is a mathematical object consisting of a set of nodes and a set of edges. Each edge in a graph connects two nodes. In a graph representing the extended LAN, the nodes represent the segments and bridges and the edges represent the connections, in the extended LAN, between the segments and bridges. This graph is called the network topology graph. The network topology graph is also referred to simply as the topology.
Using bridges to create LAN-to-LAN interconnections allows each host on the attached LANs to communicate with the other hosts on the attached LANs as if those hosts were on a same LAN. To emphasize that the interconnection of LANs using a bridge is transparent to hosts communicating across the bridge, this kind of interconnection is also called transparent bridging. An example of a LAN interconnection that is not transparent is IP (Internet protocol) subnet routing.
Transparent bridging requires that the bridges dynamically maintain address information for each of their connected LANs in order to facilitate the routing of packets. Bridges learn about the presence of hosts by listening to packets passing by. From this listening, bridges obtain the addresses of hosts on their connected LANs. Bridges use host addresses to help make forwarding decisions.
In a network with transparent bridging, the forwarded copy of a packet must be bit-for-bit identical with the original packet. Since the forwarded copy of a packet looks just like the original, it is difficult to learn exactly where hosts are located by listening to packets passing by. If a decision is made to allow forwarding of a packet in a loop, the packet would cycle endlessly in the network consuming huge amounts of bandwidth. Therefore the bridges must take care in their packet forwarding decisions never to allow any packet to be forwarded in a loop.
The Institute of Electrical and Electronics Engineering (IEEE) standard for bridged Ethernet (IEEE Std 802.1D-1993) prevents forwarding loops and solves the learning problem by classifying certain connections as active connections and the remainder as standby connections. Host packets travel only on active connections. This means that a bridge never transmits a host packet on a standby connection, and any packet a bridge might receive from a host on a standby connection is ignored. The active connections are selected so as to form a spanning tree in the network topology graph. For control purposes, one bridge is selected as the root of the spanning tree but selection of the root does not affect packet forwarding in any way. In the spanning tree of a network topology graph, for any two segments, S and D, there is exactly one path of active connections from S to D and, hence, only one path that packets from S to D can follow. Multicast packets also follow the spanning tree. When a bridge receives a multicast packet on an active connection it forwards the packet onto all of its other active connections. This results in copies of the multicast packet traveling over all active connections in the network and hence over all segments. This process is called flooding.
As previously mentioned, bridges solve the learning process by listening to packets passing by. The learning problem is solved because any host packets that a bridge hears arriving on an active connection must be from hosts that can be reached only by transmitting back on this active connection. By listening to packets the bridge learns which of its active connections to use to reach a given host. In other words, the bridge learns the direction (in the spanning tree) to a given host. Initially, none of the bridges knows the direction to any host after the bridges have selected the spanning tree. Similarly, when a bridge receives a packet (on an active connection) it may not know yet the direction to the packet""s destination host. In this case, it forwards the packet onto all of its other active connections in the same manner as a multicast packet. Thus, when no bridge knows the direction to the destination host, the packet is flooded to all segments. Conversely, when bridge receives a packet and it knows the direction to the packet""s destination host, the bridge forwards the packet onto a single connection just in this direction. The bridge forwards the packet unless the connection in the direction of the destination host is the same connection on which the packet was received. In this case the bridge discards the packet.
When packets are forwarded by flooding, the bandwidth of the extended LAN is limited to the bandwidth of a single LAN. By learning the location of hosts and forwarding packets only in the direction of the destination host, it is possible that the effective total bandwidth of the extended LAN may exceed that of a single LAN. In particular, if hosts communications occurs primarily between hosts that share the same segment, then after the location of these hosts is learned by the bridges, the bridges do not have to forward any of the shared-segment communications.
However, as the scale of an extended LAN increases, the total amount of communication between hosts on different segments tends to increase, if only because most workstations want occasional access to shared severs such as a corporate web server or corporate database. The result is that more and more packets must travel over more and more connections in the spanning tree and eventually the bandwidth through some bridge or segment is exhausted. This bandwidth limitation on an extended LAN scale arises even if the segments in the network are richly connected. The additional connections provide no benefit because the spanning tree design requires that redundant connections be classified as standby and not used for the forwarding of packets. It can easily happen that hosts separated by no more than a few bridges are forced to communicate through many bridges through a long path that follows the spanning tree. Sometimes a careful choice of spanning tree can alleviate this problem. However, as the scale of the extended LAN increases, eventually no spanning tree design can overcome such bandwidth limitation. This bandwidth scaling problem is referred to as the level-2 mesh (L2-mesh) problem.
Conventional approaches to mitigating the L2-mesh problem are the crossover, replication, and envelope techniques. The crossover technique takes advantage of a segment, S, that is connected to exactly two bridges, A and B; although one of the connections is standby and therefore cannot be used for forwarding packets according to the IEEE standard spanning tree method. As part of the learning, bridge A learns the set of addresses LT(A) of hosts that are lower in the spanning tree than A. That is, bridge A learns addresses of hosts that lie in a direction further away from the root bridge than A. Likewise bridge B learns the analogous set LT(B). Assuming that the two bridges, A and B, are on separate branches of the spanning tree (which means that it is impossible for LT(A) and LT(B) to have any addresses in common). The two bridges can privately exchange their knowledge LT(A) and LT(B). The bridges can also agree to forward packets across segment S, where each of the bridges, A and B, knows the packets to be destined to hosts below the other bridge. The crossover technique improves the performance of some but not all host-to-host communication, and requires careful selection of the spanning tree to get the branches and the cooperating bridges situated correctly.
The replication technique replicates the network by creating a plurality of virtual universes. Each universe contains its own spanning tree with its own root bridge. Each of the spanning trees covers the entire network. A packet is correlated to one of the plurality of universes based on a hash of the packet""s source and destination addresses. The packet is processed exclusively in that universe. Since, in general, a connection will be active in some universes and standby in the others, the replication technique utilizes a greater number of connections and, to a certain degree, helps spread the communication load more evenly. However, the replication technique requires bridges to learn the location of hosts in each universe separately. Also, the replication technique gives no guarantee of a short communication path; and two hosts might hash into a universe with a spanning tree that unfortunately requires them to communicate via a long path through many bridges.
The envelope technique wraps forwarded packets with an envelope so that they can be identified as packets xe2x80x9cin-route.xe2x80x9d An envelop may be implemented by embedding the original packet inside a larger data frame, in which case there is a problem of handling maximum size original packets. Alternatively, an envelope may be implemented by first sending a xe2x80x9cheraldxe2x80x9d packet to announce the upcoming forwarded packet. The wrapped packet is forwarded by conventional routing mechanisms to its destination segment whereupon it is unwrapped and sent to the destination host. The envelope technique requires additional bandwidth to handle the wrapping.
None of these techniques guarantees to send packets on the shortest communication paths without requiring extra bandwidth. Hence, there remains a need to mitigate the L2-mesh problem. There is a further need to configure bridged networks with the capacity to mitigate the L2-mesh problem and to produce improved bandwidth in packets communication. Moreover, there is a need to effectively and efficiently manage the bridged network topology and host location changes. The present invention addresses these and related problems.
The present invention provides a bridged network with so called smart bridges configured to provide effective and efficient management of the bridged network topology and host location changes. These bridges are considered smart to distinguish them from other bridges that do not embody the present invention as will be further described herein. The smart bridges are further configured to provide a transparent shortest paths routing in the bridged network. In accordance with the purpose of the invention as embodied and broadly described herein, the bridged network with the smart bridges is configured to mitigate the L2-mesh problem and to produce an improved bandwidth in packets communication.
As embodied and broadly described herein, the invention relates to computer communications networks for interconnecting computers. The transparent shortest path routing improves the overall performance of such networks through implementation of a suite of functions. These functions include inventory construction, topology acquisition, communications initialization, communications operation, and location revision.
The inventory construction is performed in cooperation by the bridge ports connected to a given segment. It compiles a list (the xe2x80x9cinventoryxe2x80x9d) of the bridge ports connected to the segment and delivers this list to each of these bridge ports. The inventory is kept up to date, so that the bridge ports are informed when any change occurs regarding their segment. When an inventory change occurs, topology acquisition is initiated.
The topology acquisition is performed in cooperation by all the bridges in the network. Topology acquisition spreads through the network via a propagation function, gathers a description of all bridge-to-segment connections (the xe2x80x9ctotal network reportxe2x80x9d) via a collection function and then delivers the total network report to all bridges via a distribution function. The propagation function also prompts a suspension of communications operation.
The communications initialization is performed by each bridge separately based on the total network report delivered during the distribution function. Communications initialization creates an internal representation of the network topology graph from the total network report, performs a global assignment of index numbers to segments and bridges, and decides how packets are to be routed. The routing decisions are recorded in various tables that will be described later. Three different types of routing are provided: location revision routing for forwarding location revision requests, network flood routing for forwarding a packet to multiple destinations or to a destination whose location is unknown, and best path routing for forwarding a packet along a shortest path to a single destination whose location is known. Once communications initialization is complete, the bridge resumes communications operation.
The communications operation is responsive to host packets. Communications operation performs its activities based on the routing tables determined by communications initialization, and based on the hosts location (HLOC) table, which is managed by location revision. Communications operation learns the locations of hosts, detects changes in the locations of hosts, expires stale information about the locations of hosts, and forwards host packets.
The location revision is performed in cooperation by all bridges in the network. Based on the location revision routing determined by communications initialization, location revision collects reports of host locations at a central, root bridge. Location revision then distributes these reports to all bridges using a wavefront protocol. Based on the arriving wavefronts, location revision manages the HLOC table. The wavefront protocol provides a barrier between bridges xe2x80x9caheadxe2x80x9d of the wavefront, which continue to use the old host location information, and bridges xe2x80x9cbehindxe2x80x9d the wavefront, which use the new host location information.
The system aspect of the invention for providing a transparent shortest path routing in a network includes network segments and at least one bridge, the bridge is relaying packets from one of the network segments to the next. The bridge is configured to perform a suite of functions including inventory construction, topology acquisition, communications initialization, communications operation, and location revision.
In accordance with a purpose of the invention, as embodied and broadly described herein, the invention relates to a method for managing end stations locations in a bridged network. The method includes providing a smart bridge, and performing in the smart bridge communications operation using a network flood active port connections (NFA) table, a network flood reaching (NFR) table, a best path forwarding (BPF) table and a best path sourcing (BPS) table. The method further includes performing in the smart bridge an end stations locations revision which manages a host location (HLOC) table. The communications operation invokes the end stations locations revision upon detecting changes in any end station location in order to prevent different smart bridges from using different end stations locations for a same end station that changed its location.
The end stations locations revision exchanges location revision packets with other smart bridges in the bridged network according to a location revision grandparent (LRG), a location revision child (LRC) table and a location revision wavefront distribution protocol. The end stations locations revision passes the location revision request from the smart bridge via the LRG of the smart bridge up along a location revision spanning tree (LRST) over a topology of the bridged network until a root of the LRST is reached unless the smart bridge is the root of the LRST, the location revision request passing from one respective LRG to a next respective LRG until the root is reached. A location revision wavefront starts at the root and, in cooperation with other smart bridges in the bridged network, spreads to the other smart bridges a location revision request for revising the HLOC of each of the other smart bridges. The location revision wavefront spreads through the bridged network by means of a wavefront protocol which governs bridge-to-bridge exchange of location revision wavefront packets. The root assigns a serial number including an index number to each location revision wavefront the root originates so that each smart bridge forwards the location revision request together with the serial number in order to indicate whether the location revision request pertains to a new or old location revision wavefront. Receipt of a location revision wavefront packet prompts the start of the end stations locations revision in which the location revision wavefront packet provides a wavefront index, a HLOC table index, a host address, identification of the segment to which the host is attached and the source address of the packet.
Advantages of the invention will be set forth, in part, in the description that follows and, in part, will be understood by those skilled in the art from the description herein. The advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the appended claims and equivalents.